package com.ly.algorithm.leetcode;
import	java.util.List;
import	java.util.LinkedList;

import java.util.ArrayList;

/**
 * @Classname Problem216
 * @Description
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1.txt - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * 说明：
 *
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1.txt:
 *
 * 输入: k = 3, n = 7
 * 输出: [[1.txt,2,4]]
 * 示例 2:
 *
 * 输入: k = 3, n = 9
 * 输出: [[1.txt,2,6], [1.txt,3,5], [2,3,4]]
 *
 *
 * @Date 2020/9/11 17:29
 * @Author 冷心影翼
 */
public class Problem216 {

    public static void main(String[] args) {
        Solution216 solution216 = new Solution216();
        List<List<Integer>> lists = solution216.combinationSum3(3, 7);
        for(List<Integer> list: lists) {
            System.out.println(list);
        }
    }

}

class Solution216 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> result = new ArrayList<>();
        LinkedList<Integer> path = new LinkedList<>();
        dfs(result,path,1,k,n);
        return result;
    }

    public void dfs(List<List<Integer>> res,LinkedList<Integer> path,int i,int k,int n) {
        if(path.size() == k){
            if(n==0)
                res.add(new ArrayList<>(path));
            return;
        }
        for(int j=i;j<=9;j++) {
            path.add(j);
            dfs(res,path,j+1,k,n-j);
            path.removeLast();
        }
    }
}